package o20_05.o01_复杂度;

import o19_10_11.MyTime;

public class FibonacciTest01 {

    /**
     * 0 1 1 2 3 5 8
     * 斐波那契数  后面 = 前面 2个 相加
     * @param args
     */
    public static void main(String[] args) {
        MyTime.naTime(() -> {
            System.out.println(fib(32)); // 最久的 几分钟 没结果
        });
        MyTime.naTime(() -> {
            System.out.println(fib2(70)); // 最久的 几分钟 没结果
        });
    }

    /**
     * 第一代快很多
     * @param n
     * @return
     */
    public static long fib2(long n) {
        if (n <= 1) return n;

        long first = 0;
        long second = 1;
        long count = n - 1;
        for (long i = 0; i < count; i++) {
            long sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }


    /**
     * 最久的
     * @param n
     * @return
     */
    public static long fib(long n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }

}
